############################
# author：码农小易
# blog：https://blog.csdn.net/csdn_xiaoyi
# 贪心算法尝试解完全背包问题
################################################################################################################
# 问题：
# 有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。第 i 种物品的体积是 c，价值是 w。
# 求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。
################################################################################################################

def go(max_bag_weights, volume_list, weights_list):
    total_value = 0                                         #统计当前装在的容量数
    bag_weights = max_bag_weights                           #背包剩余承载重量
    blocks = []
    for index, data in enumerate(volume_list):              #将物品的体积c与价值w绑定在一起，形成一个整体加入到blocks中
        blocks.append((data, weights_list[index]))          #例子：[(40, 500), (10, 200), (30, 400), (20, 450), (5, 20)]

    blocks.sort(key=lambda x: (x[1], -x[0]), reverse=True)  #以物品的价值进行从高到低的排序，如果价值相同则按照重量从低到高排序
    
    for block in blocks:
        value = block[1]                                    #物品价值
        weights = block[0]                                  #物品重量
        if (count := bag_weights // weights) > 0:           #计算当前物品能最大放入背包的个数，且个数需要>0即能放入才能执行以下两条代码
            bag_weights -= weights * count                  #计算放入背包的数个物品后剩余的重量
            total_value += value * count                    #计算放入背包的数个物品一共的价值
    
    return total_value

################################################################################################################
# 并非所有情况能得出最优解：
# 不难发现贪心算法来解背包问题，可能还存在背包装不满的问题。
################################################################################################################

def main():
    V = int(input('背包最大容量：'))
    N = int(input('物品数量：'))
    print('i: ' + '  '.join([str(i+1) for i in range(N)]))
    c = list(map(int, input('c:').split()))
    w = list(map(int, input('w:').split()))

    print('total value:', go(V,c,w))

if __name__ == "__main__":
    main()